package slidingWindows;

import java.util.ArrayList;
import java.util.List;

public class findAnagrams {
    //暴力解法
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret=new ArrayList<>();
        int[] hash1=new int[26];
        char[] s1=s.toCharArray();
        char[] s2=p.toCharArray();
        for(char a:s2){
            hash1[a-'a']++;
        }
        for(int i=0;i<s1.length-s2.length+1;i++){
            int[] hash2=new int[26];
            int count=1;
            for(int j=i;j<s2.length+i;j++){
                hash2[s1[j]-'a']++;
            }
            for(char a:s2){
                if(hash2[a-'a']!=hash1[a-'a']){
                    count=0;
                };
            }
            if(count==1){
                ret.add(i);
            }
        }
        return ret;
    }

    //滑动窗口
    public List<Integer> findAnagrams2(String ss, String pp) {
        List<Integer> ret=new ArrayList<>();
        int[] hash1=new int[26];
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();
        for(char a:p){
            hash1[a-'a']++;
        }
        int[] hash2=new int[26];
        int m = p.length;

        for(int left=0,right=0,count=0;right<s.length;right++){
            char in=s[right];
            hash2[in-'a']++;
            if(hash2[in-'a']<=hash1[in-'a']){
                count++;
            }
            if(right-left+1>m){
                char out=s[left];
                left++;
                if(hash2[out-'a']<=hash1[out-'a']){
                    count--;
                }
                hash2[out-'a']--;
            }
            if(count==m){
                ret.add(left);
            }
        }
        return ret;
    }
}
